package graphgenetics;

/**
 * @author jeremy
 */
public class TreeGenerator {
    
    private boolean[][] graph;
    private int maxLine;
    private Node[] nodes;
    private Node root;

    public TreeGenerator(int size) {
        nodes = new Node[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new Node(i);
        }
    }

    public void makeTree(boolean[][] graph, int[] order) {
        this.graph = graph;
        maxLine = 0;
        if (root != null) {
            root.breakTree();
        }
        root = nodes[order[0]];
        for (int i = 1; i < order.length; i++) {
            root.addNode(nodes[order[i]]);
        }
    }

    public int getMaxLine() {
        return maxLine;
    }

    /**
     * Stores a value and its red and blue number, and connects to
     * two other Nodes.
     */
    class Node {
        public int value, r, b;
        public Node red, blue;

        /**
         * Creates a new node with the specified value.
         * @param value
         */
        public Node(int value) {
            r = 1;
            b = 1;
            this.value = value;
        }

        public void breakTree() {
            r = 1;
            b = 1;
            if (red != null) {
                red.breakTree();
                red = null;
            }
            if (blue != null) {
                blue.breakTree();
                blue = null;
            }
        }

        /**
         * TODO: rewrite this
         * Adds n to the "red" side if it is connected (to this node)
         * in GraphItem g,
         * or to the "blue" side if it is not connected in GraphItem g.
         * Mostly for debugging
         * @param n The Node to add to the subtree with this as the root.
         */
        public void addNode(Node n) {
            // Decide where the node should go
            if (graph[value][n.value]) {
                // The vertex is red relative to this one, add it to the red
                // side
                if (red != null) {
                    // Send it down to the red child
                    red.addNode(n);
                    return;
                } else {
                    // add it directly to this
                    n.r = r + 1; // update the red number
                    n.b = b;
                    if (r > maxLine) maxLine = r;
                    if (b > maxLine) maxLine = b;

                    // Add the Node n as the red child of this Node
                    red = n;
                    return;
                }
            } else {
                // The vertex is blue relative to this one, add it to the blue
                // side
                if (blue != null) {
                    // Send it down to the blue child
                    blue.addNode(n);
                    return;
                } else {
                    // add it directly to this
                    n.b = b + 1; // Update the blue number
                    n.r = r;
                    if (b > maxLine) maxLine = b;
                    if (r > maxLine) maxLine = r;

                    // Add the Node n as the blue child of this Node
                    blue = n;
                    return;
                }
            }
        }

        /**
         * Creates a string of the form ( value[b,r] (blue) (red) )
         * @return
         */
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(" (");
            sb.append(value);
            sb.append('[');
            sb.append(b);
            sb.append(',');
            sb.append(r);
            sb.append("]");
            if (blue != null) sb.append(blue);
            if (red != null) sb.append(red);
            sb.append(") ");
            return sb.toString();
        }


    }

}
